package com.it;

/**
 * @author : code1997
 * @date : 2021/4/20 22:47
 */
public class Hanoi {
    public static void main(String[] args) {
        hanoi(3, "A", "B", "C");
    }

    /**
     * 当n == 1的时候，将盘子直接从A->C
     * 当n > 1的时候
     *     1)将盘子从n-1个盘子从A->B
     *     2)将第n个盘子从A->C
     *     2)将n-1个盘子从B->C
     * 时间复杂度: O(2^n)
     * 空间复杂度：O(n)
     * T(n) = 2 * T(n-1) + O(1) = 2 *(2*T(n-2) + O(1)) + O(1)
     * @param n:盘子的数量
     * @param a:起点柱子
     * @param b:中间柱子
     * @param c:终点柱子
     */
    private static void hanoi(int n, String a, String b, String c) {
        if (n == 1) {
            //终止条件，直接将1从a挪动到c
            move(n, a, c);
            return;
        }
        //将n-1个盘子从a挪动到b，那么c为中间柱子
        hanoi(n - 1, a, c, b);
        //移动盘子n从a到c
        move(n, a, c);
        //将n-1个盘子从b挪动到c，那么a为中间柱子
        hanoi(n - 1, b, a, c);
    }

    private static void move(int n, String from, String to) {
        System.out.println("将盘子【" + n + "】从【" + from + "】挪动到【" + to + "】");
    }
}
